Longest Palindromic Substring(LeetCode)

文章目录

1. 1. Question:Longest Palindromic Substring
2. 2. SourceCode:
   1. 2.1. s1
   2. 2.2. s2

Question:Longest Palindromic Substring

Given a string S, find the longest palindromic substring(最长回文子串)in S. 

You may assume that the maximum length of S is 1000, and there exists one 

unique longest palindromic substring.

Note:
Make sure you understand what a palindrome means. A palindrome is a string which reads the same in both directions.

For example, "aba" is a palindome, "abc" is not.

SourceCode:

s1

//笔者提交版本；耗时：75ms；
public class Solution {
    public String longestPalindrome(String s) {
        //1.边界控制
        if(null == s || s.isEmpty()){
            return "";
        }
        
        int len = s.length();
        if(1 == len){
            return s;
        }
        
        //2.logic
        
        //2.1 构造形如“#a#a#” 的字符串
        int oriArrLen = len*2+1;
        StringBuilder oriArr = new StringBuilder(oriArrLen);
        for(int i = 0 ;i<len;i++){
            oriArr.append('#');
            oriArr.append(s.charAt(i));
        }
        oriArr.append('#');
        
        //debug
        //System.out.println(oriArr);
        
        
        int maxLen = 0;
        int start = 0,end = 0;
        //2.2从头开始遍历
        for(int mid = 2;mid < oriArrLen; mid++){
            //debug
            //System.out.println("mid"+mid);
            
            int curLen = 1;
            int i=mid-1,j=mid+1;
            for(;i>=0&&j<oriArrLen;i--,j++){
                if(oriArr.charAt(i) == oriArr.charAt(j)){
                    curLen += 2;
                }else{
                    break;
                }
            }
            
            if(maxLen < curLen){
                maxLen = curLen;
                start = i+1;
                end = j-1;
            }
            
        }
        
        //debug
        //System.out.println(start+" "+end);
        
        if(oriArr.charAt(start)=='#'){
            start++;
            end--;
        }
        StringBuilder result = new StringBuilder(len);
        
        //debug
        //System.out.println(start+" "+end);
        
        for(int i = start;i<=end;i +=2){
            result.append(oriArr.charAt(i));
        }
        
        
        return result.toString();
    }
    
}

s2

//该版本参考了Solution,采用DP；耗时：104ms；

/*
To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. 
Consider the case ''ababa''. If we already knew that ''bab'' is a palindrome, it is obvious that ''ababa'' must be a palindrome 
since the two left and right end letters are the same.

We define P(i,j)P(i,j) as following:

P(i,j)= | true,if the substring Si…Sj is a palindrome
	| false,otherwise.

 
P(i,j)={true,if the substring Si…Sj is a palindrome;false,otherwise. 
	
	Therefore,

	P(i, j) = ( P(i+1, j-1) && S_i == S_j )

The base cases are:

	P(i, i) = true P(i,i)=true

	P(i, i+1) = ( S_i == S_{i+1} ) 

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...

Complexity Analysis

Time complexity : O(n^2)

Space complexity : O(n^2)

*/


public class Solution {
    public String longestPalindrome(String s) {
        //1.边界控制
        if(null == s || s.isEmpty()){
            return "";
        }
        
        int len = s.length();
        if(1 == len){
            return s;
        }
        
        //2.logic
        //[i][j]代表从字符串位置i到j是否满足条件
        boolean[][] dpTab = new boolean[len][len];
        
		//2.1 表格初始化
        //int max = 1;
        int start = 0,end =0;
        for(int i = 0 ;i<len;i++){
            dpTab[i][i] = true;
            if(i!=len-1){
                dpTab[i][i+1] = s.charAt(i) == s.charAt(i+1);
                
                if(dpTab[i][i+1]){
                    //max = 2;
                    start = i;
                    end = i+1;
                }
            }
        }
        
		//2.2 填写表格
        //最长回文统计step为长度
        for(int step=3 ; step <= len;step++){
            //i < len-step+1 注意边界
            for(int i = 0;i < len-step+1;i++){
                int j = i+step-1;
                
                dpTab[i][j] = dpTab[i+1][j-1] && (s.charAt(i) == s.charAt(j));
                
                if(dpTab[i][j]){
                    //max = step;
                    start = i;
                    end = j;
                }
            }
        }
        
        return s.substring(start,end+1);
        
    }
}